// run: $exec < input
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>

std::set<int> legal;

int const  inf = 1 << 24;
int const maxn = 20;
int map[maxn][maxn];
int a[maxn], b[maxn];
int n, m, k, l;
int f[maxn][1 << 18];

void init()
{
	legal.clear();
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++) map[i][j] = inf;
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= (1 << n); j++) f[i][j] = inf;
}

void flyoed()
{
	for (int k = 0; k <= n; k++) {
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n; j++)
				if (map[i][j] > map[i][k] + map[k][j])
					map[i][j] = map[i][k] + map[k][j];
	}
}

int greedy()
{
	int max = 0;
	for (auto st : legal) {
		std::priority_queue<std::pair<int, int>> pq;
		for (int i = 0; i < n; i++)
			if (st & (1 << i)) pq.push({a[i], i});
		int tmp = 0;
		for (int i = 0; i < k; i++) {
			auto now = pq.top(); pq.pop();
			if (now.first <= 0) break;
			tmp += now.first;
			now.first -= b[now.second];
			pq.push(now);
		}
		max = std::max(max, tmp);
	}
	return max;
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	for (int ti = 1; ti <= T; ti++) {
		std::cout << "Case " << ti << ": ";
		std::cin >> n >> m >> k >> l;
		init();
		for (int i = 0; i < n; i++) std::cin >> a[i];
		for (int i = 0; i < n; i++) std::cin >> b[i];
		for (int i = 0, u, v, c; i < m; i++) {
			std::cin >> u >> v >> c;
			if (map[u][v] > c) map[u][v] = map[v][u] = c;
		}
		flyoed();

		for (int i = 0; i < n; i++) {
			f[i][1 << i] = map[i + 1][0];
			if (2 * map[i + 1][0] <= l) legal.insert(1 << i);
		}
		for (int st = 1; st < (1 << n); st++) {
			for (int now = 0; now < n; now++) {
				if (!(st & (1 << now))) continue;
				int tmp = st ^ (1 << now);
				for (int j = 0; j < n; j++) {
					if (!(tmp & (1 << j))) continue;
					f[now][st] = std::min(f[now][st], f[j][tmp] + map[j + 1][now + 1]);
				}
				if (f[now][st] + map[now + 1][0] <= l)
					legal.insert(st);
			}
		}

		std::cout << greedy() << '\n';
	}
}

